package sort;

/**
 * Created by Ghost on 2015/4/16.
 */
public class HeapSort {
    private int fatherOf(int idx) {
        return (idx - 1) >> 1;
    }

    private int leftC(int idx) {
        return (idx << 1) + 1;
    }

    private int rightC(int idx) {
        return (idx << 1) + 2;
    }

    private void fixHeap(int[] num, int i, int edge) {
        int lC = leftC(i);
        int rC = rightC(i);
        if (rC <= edge) {
            int biggerC = Math.max(num[lC], num[rC]);
            if (biggerC > num[i]) {
                if (biggerC == num[lC]) {
                    num[lC] = num[i];
                    num[i] = biggerC;
                    fixHeap(num, lC, edge);
                } else{
                    num[rC] = num[i];
                    num[i] = biggerC;
                    fixHeap(num, rC, edge);
                }
            }
        } else if(lC<=edge){
            if(num[lC]>num[i]){
                int t = num[lC];
                num[lC] = num[i];
                num[i] = t;
                fixHeap(num, lC, edge);
            }
        }
    }

    private void buildHeap(int[] num, int edge) {
        int i = edge;
        while (i > 0) {
            int father = fatherOf(i);
            if (num[father] < num[i]) {
                num[father] = num[father] ^ num[i];   //这三段代码是交换两个数的简便算法
                num[i] = num[father] ^ num[i];
                num[father] = num[father] ^ num[i];
            }
            fixHeap(num, i, edge);
            i--;
        }

    }


    public void heapSort(int[] num, int edge) {
        buildHeap(num,edge);
        while(edge>0){
            int t = num[0];
            num[0] = num[edge];
            num[edge] = t;
            edge--;
            fixHeap(num,0,edge);
        }
    }



    public static void main(String[] args) {
        HeapSort HeapSort = new HeapSort();
        int[] num = {6,5,4,3,2,1};
        HeapSort.heapSort(num, num.length - 1);
        for (Integer I : num) {
            System.out.println(I);
        }
    }
}
